package www.study.com;

//接雨水 https://leetcode.cn/problems/trapping-rain-water/
public class code42 {
    public static void main(String[] args) {

    }

    class Solution {
        public int trap(int[] height) {
            int[] lef = new int[height.length]; //lef[i]表示max(height[0...i-1])
            int[] reg = new int[height.length]; //reg[i]表示max(height[i+1...n])
            for(int i = 1 ; i < height.length ; i++){
                lef[i] = Math.max(lef[i - 1], height[i - 1]);
            }
            for(int i = height.length - 2 ; i > - 1 ; i--){
                reg[i] = Math.max(reg[i + 1], height[i + 1]);
            }
            int res = 0;
            for(int i = 1 ; i < height.length - 1 ; i++){
                int leOrReMin = Math.min(lef[i], reg[i]) - height[i];
                res += (leOrReMin < 0 ? 0 : leOrReMin);
            }
            return res;
        }
    }
}
